#include <iostream>
using namespace std;

int main(){
    freopen("in.txt","r",stdin);
    int t;
    cin >> t;
    for(int k=0; k<t; k++){
        int i,j;
		scanf("%d %d",&i,&j);
        int left = 0,right = 0;
        while( i !=1 && j != 1 ){
            if( i>j ){
            	left += i/j;
            	i = i%j;
            }else{
                right += j/i;
                j = j%i;
            }
        }
        if( i== 1) right += (j-1);
        if( j== 1) left += (i-1);
        printf("Scenario #%d:\n%d %d\n\n",k+1,left,right);
    }
    return 0;
}
